def knapsack(weights, values, capacity):
    """
    0-1背包问题
    weights: 物品重量列表
    values: 物品价值列表  
    capacity: 背包容量
    """
    n = len(weights)
    # dp[i][w] 表示前i个物品，容量为w时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # 构建DP表
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                # 选择：放入或不放入当前物品
                dp[i][w] = max(dp[i-1][w], 
                             values[i-1] + dp[i-1][w - weights[i-1]])
            else:
                # 不能放入当前物品
                dp[i][w] = dp[i-1][w]
    
    # 回溯找出选择的物品
    selected_items = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected_items.append(i-1)
            w -= weights[i-1]
    
    return dp[n][capacity], selected_items[::-1]

# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

max_value, selected = knapsack(weights, values, capacity)
print(f"\n背包问题：")
print(f"物品重量: {weights}")
print(f"物品价值: {values}")
print(f"背包容量: {capacity}")
print(f"最大价值: {max_value}")
print(f"选择的物品索引: {selected}")
print(f"选择的物品重量: {[weights[i] for i in selected]}")
print(f"选择的物品价值: {[values[i] for i in selected]}")